package dp;

/*
* 机器人到达指定位置方法数  给定空间（数组）长度N，最终目标位置是P，给定初始位置start和可走步数rest,求总共有多少种走法
* */
public class RobotArrived {

    //暴力递归版本  cur表示当前位置
    public static int walk1(int N,int cur,int rest,int P){
        //确定状态转移的最终情况
        if (rest == 0){
            return cur==P?1:0;
        }

        //确定状态转移的左边界情况
        if (cur==1){
            return walk1(N,2,rest - 1,P);
        }
        //确定状态转移的右边界情况
        if (cur==N){
            return walk1(N,N-1,rest -1,P);
        }

        //其余状态
        return walk1(N,cur+1,rest -1,P)+ walk1(N,cur -1,rest-1,P);
    }

    //初步改进 使用记忆化搜索，减少重复的计算  使用HashMap作为缓存 -> 使用二维数组作为缓存  减少常数时间
    public static int walkWithCache(){
        return 0;
    }

    //动态规划版本
    public static int waysDP(){
        //首先确定无效参数状态

        //确定动态规划表
       // int[][] dp= new int[N+1][K+1];
        return 0;
    }
}
